package string.leetcode.medium;

/**
 * @author bruin_du
 * @description  回文子字符串的个数
 * @date 2022/8/10 17:47
 **/
public class OfferII020_CountSubstrings {
    public int countSubstrings(String s) {
        //方法一：动态规划
        //时间复杂度:O(n^2),空间复杂度:O(n)
        method1(s);

        //方法二：中心扩展算法
        //时间复杂度:O(n^2),空间复杂度:O(1)
        return method2(s);
    }

    private int method1(String s) {
        int len = s.length();
        if (len == 1) return 1;
        char[] arr = s.toCharArray();
        boolean[][] dp = new boolean[len][len];
        int res = len;
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                int j = i + L - 1;
                if (j >= len) {
                    break;
                }
                if (arr[i] == arr[j]) {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) res++;
            }
        }
        return res;
    }

    private int method2(String s) {
        int len = s.length();
        int res = 1;
        char[] arr = s.toCharArray();
        for (int i = 0; i < len - 1; i++) {
            res += expandAroundCenter(arr, i, i);
            res += expandAroundCenter(arr, i, i + 1);
        }
        return res;
    }

    private int expandAroundCenter(char[] arr, int left, int right) {
        int res = 0;
        while (left >= 0 && right <= arr.length - 1 && arr[left] == arr[right]) {
            res++;
            left--;
            right++;
        }
        return res;
    }
}
